package arithmetic.LeetCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.TreeMap;

import org.junit.jupiter.api.Test;


/**
 * 740. 删除并获得点数
 * 给你一个整数数组 nums ，你可以对它进行一些操作。
 * 每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
 * 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
 * <p>
 * 示例2：
 * <p>
 * 输入：nums = [2,2,3,3,3,4]
 * 输出：9
 * 解释：
 * 删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
 * 之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
 * 总共获得 9 个点数。
 * <p>
 * 链接：https://leetcode.cn/problems/delete-and-earn
 *
 * @author jiangfeng on 2023/4/11
 */
public class DeleteAndEarn {

    @Test
    public void test() {
        System.out.println(deleteAndEarn(new int[] {3, 4, 2}));
        // System.out.println(deleteAndEarn(new int[]{3,1}));
        //System.out.println(deleteAndEarn(new int[]{2,2,3,3,3,4}));
    }

    public int deleteAndEarn(int[] nums) {
        // 转化成打家劫舍.
        // [3,4,2]:
        // 2 : 4
        // 有序的map,这样后面加入的元素影响不会太大.
        TreeMap<Integer, Integer> r = new TreeMap<>();
        for (int n : nums) {
            if (r.containsKey(n)) {
                int value = r.get(n);
                r.put(n, value + n);
            } else {
                r.put(n, n);
            }
        }
        // 2023-04-11 17:05:11
        // 状态转移方程: i = max{选第i个(则前一个不选),   不选第i个}
        // dp[i] = Max{dp[i+1],select}
        int i = 0;
        ArrayList<Integer>[] pb = new ArrayList[r.size()];
        int[] pbSum = new int[r.size()];
        int result = 0;
        for (HashMap.Entry<Integer, Integer> n : r.entrySet()) {
            // 1.prepre的那个 ,一定不会被干扰
            int curSum1 = i - 2 < 0 ? 0 : pbSum[i - 2];
            ArrayList<Integer> prePreSelects = i - 2 < 0 ? new ArrayList() : pb[i - 2];
            curSum1 += n.getValue();
            //  新的已经被排除过
            //if (prePreSelects.contains(n.getKey() + 1) || prePreSelects.contains(n.getKey() - 1)) {
            // 没有值
            //} else {
            // 新的没被排除过

            //}

            // 2.pre的那个,可能
            int curSum2 = i - 1 < 0 ? 0 : pbSum[i - 1];
            ArrayList<Integer> preSelects = i - 1 < 0 ? new ArrayList() : pb[i - 1];
            if (preSelects.contains(n.getKey() + 1) || preSelects.contains(n.getKey() - 1)) {
                // 应该被排除,不加分.
            } else {
                curSum2 += n.getValue();
            }


            //  3.维护当前迭代,供后续计算.
            int curSum = 0;
            ArrayList<Integer> cur = new ArrayList<Integer>();
            if (curSum1 > curSum2) {
                curSum = curSum1;
                cur.addAll(prePreSelects);
                cur.add(n.getKey());
            } else {
                cur.addAll(preSelects);
                curSum = curSum2;
            }
            pb[i] = cur;
            pbSum[i] = curSum;
            i++;

            // 4.计算全局结果
            result = Math.max(result, curSum);
        }
        return result;
    }

    public int deleteAndEarn2(int[] nums) {
        // 转化成打家劫舍.
        TreeMap<Integer, Integer> r = new TreeMap<Integer, Integer>();
        for (int n : nums) {
            if (r.containsKey(n)) {
                int value = r.get(n);
                r.put(n, value + n);
            } else {
                r.put(n, n);
            }
        }

        // 2023-04-11 17:05:11
        // 状态转移方程: i = max{选第i个(则前一个不选),   不选第i个}
        // dp[i] = Max{dp[i+1],select}
        int i = 0;
        Set<Integer> preSelects = new HashSet<>();
        int[] pbSum = new int[r.size()];
        int result = 0;
        for (HashMap.Entry<Integer, Integer> n : r.entrySet()) {
            // 1.选新
            int curSum1 = i - 1 < 0 ? 0 : pbSum[i - 1];
            //  新的已经被排除过
            if (!preSelects.contains(n.getKey() + 1) && !preSelects.contains(n.getKey() - 1)) {
                // 新的没被排除过
                curSum1 += n.getValue();
            } else {

            }
            // 2.不选新,则选的前一个. 不计入总值
            int curSum2 = i - 2 < 0 ? 0 : pbSum[i - 2];

            //  3.维护当前迭代,供后续计算.
            if (curSum1 > curSum2) {
                preSelects = new HashSet<>(preSelects);
                preSelects.add(n.getKey());
            } else {
                //preSelects = new HashSet<>(prePreSelects);
            }
            pbSum[i] = Math.max(curSum1, curSum2);
            // 4.计算全局结果
            result = Math.max(result, pbSum[i]);

            i++;
        }
        return result;
    }

    public int deleteAndEarn1(int[] nums) {
        // 转化成打家劫舍.
        // [3,4,2]:
        // 2 : 4
        HashMap<Integer, Integer> r = new HashMap();
        for (int n : nums) {
            if (r.containsKey(n)) {
                int value = r.get(n);
                r.put(n, value + n);
            } else {
                r.put(n, n);
            }
        }
        // 2023-04-11 17:05:11
        // 状态转移方程: i = max{选第i个(则前一个不选),   不选第i个}
        // dp[i] = Max{dp[i+1],select}
        int i = 0;
        Set<Integer>[] pb = new HashSet[r.size()];
        int[] pbSum = new int[r.size()];
        int result = 0;
        for (HashMap.Entry<Integer, Integer> n : r.entrySet()) {
            // 1.选新,则旧的没选
            int curSum1 = i - 1 < 0 ? 0 : pbSum[i - 1];
            Set<Integer> prePreSelects = i - 2 < 0 ? new HashSet() : pb[i - 1];
            //  新的已经被排除过
            if (prePreSelects.contains(n.getKey() + 1) || prePreSelects.contains(n.getKey() - 1)) {
                // 没有值
            } else {
                // 新的没被排除过
                curSum1 += n.getValue();
            }

            // 2.不选新,则选的前一个.
            int curSum2 = i - 1 < 0 ? 0 : pbSum[i - 1];
            Set<Integer> preSelects = i - 1 < 0 ? new HashSet() : pb[i - 1];
            if (preSelects.contains(n.getKey() + 1) || preSelects.contains(n.getKey() - 1)) {
                // 应该被排除,不加分.
            } else {
                //curSum2 += n.getValue();
            }


            //  3.维护当前迭代,供后续计算.
            int curSum = 0;
            Set<Integer> cur = new HashSet();
            if (curSum1 > curSum2) {
                curSum = curSum1;
                cur.addAll(prePreSelects);
                cur.add(n.getKey());
            } else {
                cur.addAll(preSelects);
                curSum = curSum2;
            }
            pb[i] = cur;
            pbSum[i] = curSum;
            i++;

            // 4.计算全局结果
            result = Math.max(result, curSum);
        }
        return result;
    }


}
